﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using TimetableCSP.Scheduler.Entities;

namespace TimetableCSP.Scheduler
{
	/// <summary>
	/// An implementation of the Min-conflicts local search algorithm for constraint satisfaction problems.
	/// </summary>
	public class MinConflicts
	{
		private static Random random = new Random();

		/// <summary>
		/// Attempts to find a solution to a CSP.
		/// </summary>
		/// <param name="variables">The variables.</param>
		/// <param name="constraints">The constraints.</param>
		/// <param name="maxSteps">The maximum amount of steps.</param>
		/// <param name="randomize">if set to <c>true</c> then random values will be assigned to all variables.</param>
		/// <returns>If a solution was found then a cloned list of the variables with assignments that satisfy all constraints is returned. Otherwise <c>null</c>.</returns>
		public static IEnumerable<AbstractVariable> FindSolution(AbstractVariable[] variables, IEnumerable<AbstractConstraint> constraints, int maxSteps, bool randomize)
		{
			List<Change> changeHistory = null;
			return FindSolution(variables, constraints, maxSteps, randomize, out changeHistory);
		}

		/// <summary>
		/// Attempts to find a solution to a CSP.
		/// </summary>
		/// <param name="variables">The variables.</param>
		/// <param name="constraints">The constraints.</param>
		/// <param name="maxSteps">The maximum amount of steps.</param>
		/// <param name="randomize">if set to <c>true</c> then random values will be assigned to all variables.</param>
		/// <param name="changeHistory">The changes made during each iteration of the algorithm.</param>
		/// <returns>
		/// If a solution was found then a cloned list of the variables with assignments that satisfy all constraints is returned. Otherwise <c>null</c>.
		/// </returns>
		public static IEnumerable<AbstractVariable> FindSolution(AbstractVariable[] variables, IEnumerable<AbstractConstraint> constraints, int maxSteps, bool randomize, out List<Change> changeHistory )
		{
			Stopwatch executionTime = new Stopwatch();
			executionTime.Start();
			int iterations;
			IEnumerable<AbstractVariable> solution = FindSolution_(variables, constraints, maxSteps, randomize, out iterations, out changeHistory);

#if DEBUG
			System.Diagnostics.Debug.Write(Change.ChangeHistoryToString(changeHistory));
#endif

			executionTime.Stop();
			System.Diagnostics.Debug.WriteLine("\n" + (solution == null ? "No" : "A") + " solution was found in " + iterations + " iterations");
			System.Diagnostics.Debug.WriteLine("Execution time: " + executionTime.ElapsedMilliseconds + " milliseconds");
			return solution;
		}

		/// <summary>
		/// Finds all conflicts in the supplied variable assignment.
		/// </summary>
		/// <param name="variables">The variables.</param>
		/// <param name="constraints">The constraints.</param>
		/// <returns>An array of all conflicts found.</returns>
		public static Conflict[] FindConflicts(AbstractVariable[] variables, IEnumerable<AbstractConstraint> constraints)
		{
			//
			// Split the constraints up into separate lists of unary and binary constraints.
			//
			List<UnaryConstraint> unaryConstraints;
			List<BinaryConstraint> binaryConstraints;
			SplitConstraints(constraints, out unaryConstraints, out binaryConstraints);
			//
			// Delegate to overload
			//
			return FindConflicts(variables, unaryConstraints, binaryConstraints);
		}

		/// <summary>
		/// Splits the supplied list of constraints into two lists, one for unary constratints and one for binary constraints.
		/// </summary>
		/// <param name="constraints">The entire list of constraints.</param>
		/// <param name="unaryConstraints">The unary constraints.</param>
		/// <param name="binaryConstraints">The binary constraints.</param>
		private static void SplitConstraints(IEnumerable<AbstractConstraint> constraints, 
			out List<UnaryConstraint> unaryConstraints, 
			out List<BinaryConstraint> binaryConstraints )
		{
			unaryConstraints = new List<UnaryConstraint>();
			binaryConstraints = new List<BinaryConstraint>();

			foreach (AbstractConstraint constraint in constraints)
			{
				if (constraint is UnaryConstraint)
				{
					unaryConstraints.Add((UnaryConstraint)constraint);
				}
				else if (constraint is BinaryConstraint)
				{
					binaryConstraints.Add((BinaryConstraint)constraint);
				}
				else
				{
					throw new NotSupportedException("Only unary and binary constraints are supported");
				}
			}
		}

		private static IEnumerable<AbstractVariable> FindSolution_(AbstractVariable[] variables, 
			IEnumerable<AbstractConstraint> constraints, 
			int maxSteps, 
			bool randomize,
			out int iterations, 
			out List<Change> changeHistory )
		{
			changeHistory = new List<Change>();

			//In order not to modify the original data a copy is taken.
			AbstractVariable[] variableCopy = new AbstractVariable[variables.Length];
			for (int index = 0; index < variables.Length; index++)
			{
				variableCopy[index] = (AbstractVariable)variables[index].Clone();
			}

			if (randomize == true) // Only used for the initial pass
			{
				AssignRandomValues(variableCopy);
			}

			List<UnaryConstraint> unaryConstraints;
			List<BinaryConstraint> binaryConstraints;
			SplitConstraints(constraints, out unaryConstraints, out binaryConstraints);
			
			for (int step = 0; step < maxSteps; step++)
			{
				iterations = step + 1;
 				
				//Reset the conflict count
				foreach (AbstractConstraint abstractConstraint in constraints)
				{
					abstractConstraint.ConflictCount = 0;
				}

				//Get current conflicts
				Conflict[] conflicts = FindConflicts(variableCopy, unaryConstraints, binaryConstraints);

#if DEBUG		//Output the current conflicts by conflict type.
				System.Diagnostics.Debug.Write(AbstractConstraint.ConflictInfoToString(iterations, constraints));
				System.Diagnostics.Debug.Flush();

				//System.Console.Write(AbstractConstraint.ConflictInfoToString(iterations, constraints));
				//System.Console.Out.Flush();
#endif

				//
				// If current is a solution, return current
				//
				if (conflicts.Length == 0)
				{
					return variableCopy;
				}
				//
				// var = randomly chosen conflicted variable
				//
				Conflict[] unpinnedConflicts = conflicts.Where(c => c.Variable.Pinned == false).ToArray();
				if (unpinnedConflicts.Length == 0)
				{
					//
					// There's nothing we can do, all the conflicting variables are pinned
					// TODO: Consider reporting this fact to the caller
					//
					return null;
				}
				//Picking a random unpinned conflict.
				Conflict randomConflict = unpinnedConflicts[random.Next(unpinnedConflicts.Length)];
				//
				// Find a new value for this variable that minimized the amount of conflicts
				//
				changeHistory.Add( MinimizeConflicts(variableCopy, randomConflict, unaryConstraints, binaryConstraints) );
			}
			//
			// No solution found
			//
			iterations = maxSteps;
			return null;
		}

		private static Change MinimizeConflicts(AbstractVariable[] allVariables, Conflict randomConflict, List<UnaryConstraint> unaryConstraints, List<BinaryConstraint> binaryConstraints)
		{
			//
			// Randomly select an attribute to change. This may not fly for all kinds of constraint satisfaction problems but it suffices in our case.
			//
			string attributeToChange = randomConflict.Attributes[random.Next(randomConflict.Attributes.Length)];
			//
			// Keep the original value since we don't need to check how many conflicts it causes, we already know that.
			//
			int originalValue = randomConflict.Variable[attributeToChange];
			List<int> bestSolutions = new List<int>();
			bestSolutions.Add(originalValue);
			int bestConflictCountSoFar = randomConflict.ConflictCount;
			//
			// Randomize the values in the domain. That way we can immediately return if we find a non-conflicting value.
			//
			int[] values = GetRandomizedValues(randomConflict.Variable.GetDomainCeiling(attributeToChange));
			string[] conflictingAttributes;
			foreach (int value in values)
			{
				//
				// Skip the original value, we don't need to check it again
				//
				if (value == originalValue)
				{
					continue;
				}
				//
				// Assign a new value and count the conflicts
				//
				randomConflict.Variable[attributeToChange] = value;
				int conflictCount = CountConflicts(randomConflict.Variable, allVariables, unaryConstraints, binaryConstraints, out conflictingAttributes);
				if (conflictCount == 0)
				{
					return new Change() { Variable = randomConflict.Variable, Attribute = attributeToChange, OriginalValue = originalValue, OriginalConflictCount = randomConflict.ConflictCount, ModifiedValue = value, ModifiedConflictCount = 0 };
				}
				else if (conflictCount < bestConflictCountSoFar)
				{
					bestSolutions.Clear();
					bestConflictCountSoFar = conflictCount;
				}
				if (conflictCount <= bestConflictCountSoFar)
				{
					bestSolutions.Add(value);
				}
			}
			//
			// Select one value at random from the best we found (the ones that cause the least amount of conflicts)
			//
			randomConflict.Variable[attributeToChange] = bestSolutions[random.Next(bestSolutions.Count)];
			return new Change() { Variable = randomConflict.Variable, Attribute = attributeToChange, OriginalValue = originalValue, OriginalConflictCount = randomConflict.ConflictCount, ModifiedValue = randomConflict.Variable[attributeToChange], ModifiedConflictCount = 0 };
		}

		private static int[] GetRandomizedValues(int size)
		{
			int[] values = new int[size];
			for (int index = 0; index < size; index++)
			{
				values[index] = index;
			}
			return values.OrderBy(x => random.Next()).ToArray();
		}

		private static Conflict[] FindConflicts(AbstractVariable[] variables, IEnumerable<UnaryConstraint> unaryConstraints, IEnumerable<BinaryConstraint> binaryConstraints)
		{
			List<Conflict> conflicts = new List<Conflict>();
			string[] conflictingAttributes;
			foreach (AbstractVariable variable in variables)
			{
				int conflictCount = CountConflicts(variable, variables, unaryConstraints, binaryConstraints, out conflictingAttributes);
				if (conflictCount > 0)
				{
					conflicts.Add(new Conflict() { Variable = variable, Attributes = conflictingAttributes, ConflictCount = conflictCount });
				}
			}
			return conflicts.ToArray();
		}

		private static int CountConflicts(AbstractVariable focusVariable, AbstractVariable[] allVariables, IEnumerable<UnaryConstraint> unaryConstraints, IEnumerable<BinaryConstraint> binaryConstraints, out string[] conflictingAttributes)
		{
			HashSet<string> attributeSet = new HashSet<string>();
			int conflictCounter = 0;
			//
			// Check unary constraints
			//
			foreach (UnaryConstraint unaryConstraint in unaryConstraints)
			{
				if (unaryConstraint.IsConflict(focusVariable, out conflictingAttributes))
				{
					conflictCounter++;
					attributeSet.UnionWith(conflictingAttributes);
				}
			}
			//
			// Check binary constraints
			//
			foreach (AbstractVariable variable in allVariables)
			{
				if (variable == focusVariable)
				{
					continue;
				}
				foreach (BinaryConstraint constraint in binaryConstraints)
				{
					if (constraint.IsConflict(focusVariable, variable, out conflictingAttributes))
					{
						conflictCounter++;
						attributeSet.UnionWith(conflictingAttributes);
					}
				}
			}
			conflictingAttributes = attributeSet.ToArray<string>();
			return conflictCounter;
		}

		private static void AssignRandomValues(AbstractVariable[] variables)
		{
			foreach (AbstractVariable variable in variables)
			{
				foreach (string attributeName in variable.GetAttributeNames())
				{
					variable[attributeName] = random.Next(variable.GetDomainCeiling(attributeName));
				}
			}
		}
	}
}
